package org.example.myleet.p403;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 46 ms
 * 动态规划 + 哈希表
 */
public class Solution1 {

    private static final int[] RANGE = new int[]{-1, 0, 1};

    public boolean canCross(int[] stones) {
        int len = stones.length;
        //初始化哈希表记录石头的位置
        HashMap<Integer, Integer> stoneMap = new HashMap<>();
        for (int i = 0; i < len; ++i) {
            stoneMap.put(stones[i], i);
        }
        //动态规划，保存每个石头位置有多少种跳到这块石头上的跳跃距离(K)的所有可能性
        HashSet<Integer>[] dpK = new HashSet[len];
        HashSet<Integer> dp0 = new HashSet<>();
        //初始化，0位置K=0
        dp0.add(0);
        dpK[0] = dp0;
        for (int i = 0; i < len - 1; ++i) {
            if (i > 0 && stones[i] - stones[i - 1] > i) {
                //剪枝，此种情况下一定跳不过去
                return false;
            }
            //到达该石头时可能经过的跳跃距离
            HashSet<Integer> possibleK = dpK[i];
            if (possibleK != null && !possibleK.isEmpty()) {
                for (Integer k : possibleK) {
                    //算出下一个石头的位置（nextStone）以及下一个跳跃距离（nextK），通过stoneMap找到下一个石头的下标（nextI）
                    int nextStone, nextK;
                    Integer nextI;
                    for (int r : RANGE) {
                        nextK = k + r;
                        if (nextK > 0) {
                            nextStone = stones[i] + nextK;
                            nextI = stoneMap.get(nextStone);
                            if (nextI != null && nextI > 0 && nextI <= len - 1) {
                                //找到下一个石头，记录跳跃距离
                                if (dpK[nextI] == null) {
                                    dpK[nextI] = new HashSet<>();
                                }
                                dpK[nextI].add(nextK);
                            }
                        }
                    }
                }
            }
        }
        //最后一个石头如果有跳跃距离说明可以跳到
        HashSet<Integer> possibleK = dpK[len - 1];
        return possibleK != null && !possibleK.isEmpty();
    }
}
